Regular expression search operations are employed in various applications including, for example, intrusion detection systems (IDS), virus protections, policy-based routing functions, internet and text search operations, document comparisons, and so on. A regular expression can simply be a word, a phrase or a string of characters. For example, a regular expression including the string “gauss” would match data containing gauss, gaussian, degauss, etc. More complex regular expressions include metacharacters that provide certain rules for performing the match. Some common metacharacters are the wildcard “.”, the alternation symbol “|”, and the character class symbol “[ ].” Regular expressions can also include quantifiers such as “*” to match 0 or more times, “+” to match 1 or more times, “?” to match 0 or 1 times, {n} to match exactly n times, {n,} to match at least n times, and {n,m} to match at least n times but no more than m times. For example, the regular expression “a.{2}b” will match any input string that includes the character “a” followed exactly 2 instances of any character followed by the character “b” including, for example, the input strings “abbb,” adgb,” “a7yb,” “aaab,” and so on.
For hardware-based regular expression search engines, counters are employed to count the number of characters of an input string that match a quantified character or character class of a regular expression. However, for complex regular expressions in which multiple overlapping substrings of an input string can concurrently match the regular expression, multiple counters are required to maintain a separate count value for each potentially matching substring. Because there is no limit upon the number of potentially matching substrings for search operations involving some regular expressions, using a separate counter for each potentially matching substring is not practical. Thus, there is a need for a counter circuit in a hardware-based regular expression search engine that can simultaneously maintain a plurality of separate character match count values for a plurality of overlapping input substrings that match a portion of a regular expression.
Like reference numerals refer to corresponding parts throughout the drawing figures.